This invention relates to computing and using resource colors for composite links.
In a Multiprotocol Label Switching (MPLS) network, a signaling protocol is used to set up a label switched path (LSP) in the MPLS network. As part of setting up the LSP, routers included in the MPLS network set up a label information base (LIB) that maps an incoming label from an input port of the router to an output port and a new label value. The routers forward packets along links through the MPLS network based on these labels that are attached to the packet to indicate which LSP to use. The label is typically swapped to the new label at each router hop. In this way, an LSP identifies the specific path of nodes and links that the packet takes through the MPLS network. MPLS allows label stacking, where a packet can have more than one label. The forwarding of packets along links is based on the “top of stack” label. When the “top of stack” label is “popped” (or removed), forwarding is based on the next label in the stack that is now the new “top of stack” label. Label stacking is useful for building hierarchical LSPs where several smaller, shorter-lived LSPs can be “stacked” onto a larger, longer-lived LSP. Using hierarchical LSPs can provide better scalability as the network grows in size.
Two kinds of LSPs can be set up in a network running MPLS: control driven LSPs and traffic engineered LSPs. A traffic engineered LSP through the network is established using a label distribution protocol (LDP) such as RSVP-TE (resource reservation setup protocol with traffic engineering) or CR-LDP (constraint-based LDP). The LDP also reserves network resources necessary to meet pre-defined service requirements of the LSP. Traffic engineered LSPs typically have constraints associated with them such as bandwidth requirements and maximum tolerable delay.
As a part of traffic engineering, links in the network may also be assigned a 32-bit vector called the resource class or color of the link. The color vector can be thought of as a collection of link attributes. Each color in the color vector is represented by a bit. If a bit in the color vector is asserted (is a one, as opposed to a zero) for a link, then the link possesses the attribute corresponding to that color.
Colors are useful for specifying attributes such as satellite link, terrestrial link, low security link, high security link, etc. Then, during path selection for a particular LSP, additional constraints can be specified such as: find a path for an LSP that uses only links that are not satellite links and that also have a high security. For example, a network may include the four colors red, green, blue, and black, using only four of the thirty-two available bits in the color vector. A link can be a member of zero, one, or more of these colors. The operator can specify that the LSP to be set up must include green links but not black links. Using a four-bit color vector having bits from left to right representing red, green, blue, and black, any link having a color mask of X1X0 (where X means “do not care” and may be a one or a zero) would satisfy the constraints specified by the operator, and would thus be eligible for inclusion in the path selection process for the LSP.
When computing the path for the LSP, an interior gateway protocol's (IGP) path selection process will first prune the link state database of all links that are deemed ineligible either due to insufficient bandwidth or due to possession or lack of a certain set of colors. The path selection process would then run some form of a shortest path algorithm to compute the “best” path that satisfies all of the specified constraints. After the path selection process provides the path, the LDP is used to setup the LSP at the routers along the path through the network.
Once the LSP has been computed as described above, it may be used as a “composite link” by the IGP when performing path selection to compute paths for subsequent LSPs. In other words, the LSP that was setup can be treated as though it were a physical link in the network. New LSPs are basically “stacked” onto the LSP corresponding to the composite link. Just as is done for regular physical links, the IGP routing protocols such as OSPF (open shortest path first) and IS—IS (intermediate system to intermediate system) can also advertise information about the composite link such as its bandwidth and color vector. The composite link's color vector should represent the attributes of all of its links, each of those links having its own color vector.